#include <iostream>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;

//// 公式法求欧拉函数
// LL get_phi(LL x)
// {
//     LL ret = x;
//     for(int i = 2; i <= x / i; i++)
//     {
//         if(x % i == 0)
//         {
//             ret = ret / i * (i - 1);
//             while(x % i == 0) x /= i;
//         }
//     }
//     if(x > 1) ret = ret / x * (x - 1);
//     return ret;
// }

// 欧拉筛打表欧拉函数
bool st[N];
int cnt;
LL p[N];
LL phi[N];

LL get_phi(LL n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            p[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; 1ll * i * p[j] <= n; j++)
        {
            int x = i * p[j];
            st[x] = true;
            if(i % p[j] == 0)
            {
                phi[x] = p[j] * phi[i];
                break;
            }
            else 
            {
                phi[x] = (p[j] - 1) * phi[i];
            }
        }
    }
   
}

int main()
{
    // LL x; cin >> x;
    // LL ret = get_phi(x);
    // cout << ret << endl;

    LL n; cin >> n;
    get_phi(n);
    for(int i = 2; i <= n; i++) cout << i << " " << phi[i] << endl;
    return 0;
}